package leetcode

type Tree struct {
	// 值
	Val int
	// 左子节点指针
	Left *Tree
	// 右子节点指针
	Right *Tree
	// 是否是根节点
	IsRoot bool
}

// 前序遍历
func (t *Tree) PreOrder(v *[]int) {
	if t == nil {
		return
	}
	*v = append((*v), t.Val)
	t.Left.PreOrder(v)
	t.Right.PreOrder(v)
}

func (t *Tree) PreOrderStack(v *[]int) {
	if t == nil {
		return
	}
	var treeStack []*Tree
	treeStack = append(treeStack, t)
	var cur = t
	for len(treeStack) > 0 {
		cur = treeStack[len(treeStack)-1]
		treeStack = treeStack[:len(treeStack)-1]
		*v = append((*v), cur.Val)
		if cur.Right != nil {
			treeStack = append(treeStack, cur.Right)
		}
		if cur.Left != nil {
			treeStack = append(treeStack, cur.Left)
		}
	}
}

// 中序遍历
func (t *Tree) InOrder(v *[]int) {
	if t == nil {
		return
	}
	t.Left.InOrder(v)
	*v = append((*v), t.Val)
	t.Right.InOrder(v)
}

// 后序遍历
func (t *Tree) PostOrder(v *[]int) {
	if t == nil {
		return
	}
	t.Left.PostOrder(v)
	*v = append((*v), t.Val)
	t.Right.PostOrder(v)
}
